/*
题目描述：在排序数组中查找数字
方法：分别利用二分查找找到第一次k出现的位置和最后一次出现的位置
 */
public class E53 {
    public static void main(String[] args) {
        int[] array = {1,2,3,3,3,3,4,5};
        int k = 3;
        int res = GetNumberOfK(array, k);
        System.out.println(res);
    }

    public static int GetNumberOfK(int [] array , int k) {
        int times = 0;
        if(array != null && array.length > 0){
            int first = GetFirstK(array, k, 0, array.length - 1);
            int last = GetLastK(array, k, 0, array.length - 1);
            if(first > -1 && last > -1){
                times = last - first + 1;
            }
        }
        return times;
    }

    public static int GetFirstK(int[] array, int k, int start, int end){
        if(start > end){
            return -1;
        }
        int midIndex = (end + start) / 2;
        int midData = array[midIndex];
        if(midData == k){
            //确定是第一个k
            if((midIndex > 0 && array[midIndex - 1] != k)
                ||midIndex == 0){
                return midIndex;
            }
            else{
                end = midIndex - 1;
            }
        }
        else if(midData > k){
            end = midIndex - 1;
        }
        else{
            start = midIndex + 1;
        }
        return GetFirstK(array, k, start, end);
    }

    public static int GetLastK(int[] array, int k, int start, int end){
        if(start > end){
            return -1;
        }
        int midIndex = (end + start)/2;
        int midData = array[midIndex];

        if(midData == k){
            if((midIndex < array.length - 1 && array[midIndex + 1] != k)
                || midIndex == array.length - 1){
                return midIndex;
            }
            else{
                start = midIndex + 1;
            }
        }
        else if(midData > k){
            end = midIndex - 1;
        }
        else{
            start = midIndex + 1;
        }
        return GetLastK(array, k, start, end);
    }
}
